#include "stack_queue.h"

void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}

void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}

listNode::listNode(){
    this->next = NULL;
}

listNode::listNode(int val, listNode* suc){
    this->data = val;
    this->next = suc;
}

//add
listNode::listNode(char val, listNode* suc){
    this->data = val;
    this->next = suc;
}

/***************STACK******************/
MyStack::MyStack(){
    this->stackSize = 0;
    this->topNode = NULL;
}

MyStack::~MyStack(){
    while (this->topNode != NULL)
    {
        listNode *tmp = this->topNode;
        this->topNode = tmp->next;
        delete tmp;
        this->stackSize--;
    }
    
}

bool MyStack::push(const int& item){
    listNode *newNode = new listNode(item, NULL);
    if (newNode == NULL)
    {
        return false;
    }
    newNode->next = this->topNode;
    this->topNode = newNode;
    this->stackSize++;
    return true;
}

bool MyStack::pop(int& item){
    if (this->topNode == NULL)
    {
        return false;
    }
    listNode *tmp = this->topNode;
    item = tmp->data;
    this->topNode = this->topNode->next;
    delete tmp;
    this->stackSize--;
    return true;
}

bool MyStack::getTop(int& item){
    if (this->topNode == NULL)
    {
        return false;
    }
    item = this->topNode->data;
    return true;
}

//add
bool MyStack::push(const char& item){
    listNode *newNode = new listNode(item, NULL);
    if (newNode == NULL)
    {
        return false;
    }
    newNode->next = this->topNode;
    this->topNode = newNode;
    this->stackSize++;
    return true;
}

bool MyStack::pop(){
    if (this->topNode == NULL)
    {
        return false;
    }
    listNode *tmp = this->topNode;
    this->topNode = this->topNode->next;
    delete tmp;
    this->stackSize--;
    return true;
}

bool MyStack::getTop(char& item){
    if (this->topNode == NULL)
    {
        return false;
    }
    item = this->topNode->data;
    return true;
}

bool MyStack::isEmpty(){
    if (this->topNode == NULL)
    {
        return true;
    }
    return false;
}


/******************QUEUE************************/

MyQueue::MyQueue(const int& capac){
    this->capacity = capac;
    this->front = 0;
    this->rear = 0;
    this->queue = new int[capac];
}
 
MyQueue::~MyQueue(){}

bool MyQueue::enQueue(const int& item){
    if ((rear + 1) % capacity == front)
    {
        return false;
    }
    
    queue[rear] = item;
    rear = (rear + 1) % capacity;
    return true;
}

bool MyQueue::deQueue(int& item){
    if ((front == rear) || (front + 1) % capacity == rear)
    {
        return false;
    }
    
    item = queue[front];
    front = (front + 1) % capacity;
    return true;
}

bool MyQueue::getFront(int& item){
    if ((front == rear) || (front + 1) % capacity == rear)
    {
        return false;
    }
    item = queue[front];
    return true;
}

bool MyQueue::isFull(){
    if ((rear + 1) % capacity == front)
    {
        return true;
    }
    
    return false;
}

// 设置优先级
int isp(char c){
    if (c == '#')return 0;
    if (c == '(')return 1;
    if (c == '^')return 7;
    if (c == '*' || c == '/' || c == '%')return 5;
    if (c == '+' || c == '-')return 3;
    if (c == ')')return 8;
    return -1;
}

int icp(char c){
    if (c == '#')return 0;
    if (c == '(')return 8;
    if (c == '^')return 6;
    if (c == '*' || c == '/' || c == '%')return 4;
    if (c == '+' || c == '-')return 2;
    if (c == ')')return 1;
    return -1;
}

bool isdigit(char c){
    if (c >= '0' && c <= '9')
    {
        return true;
    }
    return false;
}


bool postfixExpression(const string& expr, string& result){
    result = "";
    MyStack exps;
    exps.push('#');
    char ch, op;
    string tmpstr = expr + '#';
    ch = tmpstr[0];
    // 开头既不是数字也不是'('
    if (!isdigit(ch) && ch != '(')
    {
        result = "Expression is wrong!";
        return false;
    }
    int idx = 0;
    while (!exps.isEmpty() && ch != '#')
    {
        if (isdigit(ch))
        {
            result += ch;
            idx ++;
            ch = tmpstr[idx];
        }
        else{
            char tmp;
            exps.getTop(tmp);
            if (isp(tmp) < icp(ch))
            {
                // 比 栈外')'还小的只有'#'，说明没有相匹配的'('，故错误
                if (ch == ')')
                {
                    result = "Expression is wrong!";
                    return false;
                }
                //
                // 一般 '(' 左边都是操作符，所以如果为操作数，都是错误表达式
                if (ch == '(' && isdigit(tmpstr[idx-1]))
                {
                    result = "Expression is wrong!";
                    return false;
                }
                exps.push(ch);
                idx ++;
                ch = tmpstr[idx];
            }else if (isp(tmp) > icp(ch))
            {
                // 一般 ')' 左边都是操作数，所以如果为操作符，都是错误表达式
                if (ch == ')' && !isdigit(tmpstr[idx-1]))
                {
                    result = "Expression is wrong!";
                    return false;
                }
                exps.getTop(op);
                exps.pop();
                result += op;
            }else {
                //判断'()'内是否有内容，没有则为错误表达式：()*7-2
                if (ch == ')' && tmpstr[idx - 1] == '(')
                {
                    result = "Expression is wrong!";
                    return false;
                }
                exps.pop();
                if (tmp == '(')
                {
                    idx++;
                    ch = tmpstr[idx];
                }
            }
        }
    }
    while (!exps.isEmpty())
    {
        char t;
        exps.getTop(t);
        exps.pop();
        char nt;
        exps.getTop(nt);
        if (isp(t) < isp(nt) || t == ')' || t == '(')
        {
            result = "Expression is wrong!";
            return false;
        }
        if (t != '#')
        {
            result += t;
        }   
    }
    return true;
}

bool expressionVal(const string& expr, int& result){
    string postexpr;
    result = 0;
    bool flag = postfixExpression(expr, postexpr);
    if (flag)
    {
        MyStack opnd;
        for (auto ch : postexpr)
        {
            if (isdigit(ch))
            {
                int num = ch - '0';
                opnd.push(num);
            }else {
                int op1, op2;
                opnd.getTop(op2);
                opnd.pop();
                opnd.getTop(op1);
                opnd.pop();
                switch (ch)
                {
                    int res;
                    case '*': 
                        res = op1 * op2;
                        opnd.push(res);
                        break;
                    case '/': 
                        res = op1 / op2;
                        opnd.push(res);
                        break;
                    case '+': 
                        res = op1 + op2;
                        opnd.push(res);
                        break;
                    case '-': 
                        res = op1 - op2;
                        opnd.push(res);
                        break;
                    
                    default:
                        break;
                }
            }
        }
        opnd.getTop(result);
        return true;
    }
    
    return false;
}

void yanghui(const int& size){
    MyQueue q(size + 3);
    q.enQueue(1);
    q.enQueue(1);

    int s = 0;
    for (int i = 1; i <= size; i++)
    {
        q.enQueue(0);
        for (int j = 1; j <= i + 2; j++)
        {
            int item;
            q.deQueue(item);
            q.enQueue(s + item);
            s = item;
            if (j < i + 1)
            {
                cout<<s<<",";
            }else if (j == i + 1)
            {
                cout<<s;
            }
        }
        cout<<endl;
    }
}
